// 处理输入输出
// 封装getResult
// 可能需要用到装水桶理论解题
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let limit;
let n;
let initArr = []; // 元素为[开始, 结束]


rl.addListener("line", (line) => {
    if (limit === undefined) {
        limit = Number(line.trim())
    } else if (n === undefined) {
        n = Number(line.trim())
        // 截断条件
        if (n === 0) {
            console.log(0)
            rl.close();
        }
    } else {
        let temp = line.trim().split(" ").map(Number)
        initArr.push(temp);
        if (initArr.length === n) {
            const result = getResult(limit, n, initArr);
            console.log(result)
            //todo收尾
            limit = undefined;
            n = undefined;
            initArr.length = 0;

        }
    }

})

/**
 *
 * @param limit 限量
 * @param n 面试场次
 * @param initArr 面试场次信息
 * @returns {number} 需要面试官数
 */
function getResult(limit, n, initArr) {
    // 使用木桶理论, 判断是否可以插入当前桶
    if (n === 0) return 0;
    // todo 对initArr进行排序
    let buckets = new Array(n).fill(0).map(_ => []); // 初始化桶
    buckets[0].push(initArr[0])

    outer: for (let i = 1; i < initArr.length; i++) {
        let arr = initArr[i];
        inner: for (let j = 0; j < buckets.length; j++) {
            if (confirm(buckets, j, arr, limit)) {
                buckets[j].push(arr)
                break inner;
            }
        }
    }

    // 计算有容量的木桶数
    return buckets.reduce((acc, arr) => {
        if (arr.length){
            return ++acc
        }
        return acc
    }, 0)
}

/**
 *
 * @param buckets 桶数组
 * @param j 往第几个桶装
 * @param arr 要装的数据
 * @param limit 桶容量
 * @return {boolean} 是否能装
 */
function confirm(buckets, j, arr, limit) {
    let tempArr = buckets[j];
    // 判断桶的容量是否OK
    if (tempArr.length >= limit) return false;

    // 判断是否都没有交集
    return !tempArr.some((childArr) => {
        const childLeft = childArr[0]
        const childRight = childArr[1]
        const currentLeft = arr[0]
        const currentRight = arr[1]
        return !(childLeft <= currentRight || childRight <= currentLeft);
    })
}